package com.lfg.leetcode.leetcode100;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class No133cloneGraph {

    public static void main(String[] args) {
        Node node0 = new Node(0);
        Node node1 = new Node(1);
        Node node2 = new Node(2);

        node1.neighbors.add(node2);
        node2.neighbors.add(node2);

        node0.neighbors.add(node2);
        node0.neighbors.add(node1);

        Node ret = cloneGraph(node0);
        System.out.println(ret);
    }

    public static Node cloneGraph(Node node) {
        if (null == node) {
            return node;
        }
        Map<Integer, Node> map = new HashMap<>();
        return cloneGraph(node, map);
    }

    public static Node cloneGraph(Node node, Map<Integer, Node> map) {
        Node ret = map.get(node.val);
        if (ret != null) {
            return ret;
        }
        ret = new Node(node.val);
        map.put(node.val, ret);
        for (Node e : node.neighbors) {
            ret.neighbors.add(cloneGraph(e, map));
        }
        return ret;
    }


    static class Node {
        public int val;
        public List<Node> neighbors;
        public Node() {
            val = 0;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val) {
            val = _val;
            neighbors = new ArrayList<Node>();
        }
        public Node(int _val, ArrayList<Node> _neighbors) {
            val = _val;
            neighbors = _neighbors;
        }
    }
}